#ifndef CONTAINERHELPER_H
#define CONTAINERHELPER_H

#include <Qt>
#include <QtAlgorithms>
#include <QVariantList>

template <typename Type> class QList;
template <typename Type1, typename Type2> struct QPair;
class QStringList;
class QVariant;
typedef QList<QVariant> QVariantList;

namespace ContainerHelper
{
    template <typename Container, typename Type> int lowerBound (const Container& container, const Type &value);
    template <typename Container, typename Type, typename LessThan> int lowerBound (const Container& container, const Type &value,
                                                                                    LessThan lessThan);
    template <typename Container, typename Type> int upperBound (const Container& container, const Type &value);
    template <typename Container> QVariantList toVariantList (const Container& container);
#ifndef QT_NO_DEBUG
    template <typename Container> bool isSorted (const Container& container);
    template <typename Container, typename LessThan> bool isSorted (const Container& container, LessThan lessThan);
#endif
}

// global namespace
template <typename Container, typename LessThan> void qSort (Container& container, LessThan lessThan);
class StringNumericalLess;
bool compareVariants (QVariant first, QVariant second);

// Performs a binary search on the container and returns the position of the first occurrence
// of value. If no such item is found, returns the position where the item should be inserted.
// The items in the container must be sorted in ascending order.
// Similar to qLowerBound, but returns integer instead of iterator.
template <typename Container, typename Type, typename LessThan>
int ContainerHelper::lowerBound (const Container& container, const Type &value, LessThan lessThan)
{
    int begin = 0;
    int n = container.size();
    while (n > 0)
    {
        int half = n >> 1;
        int middle = begin + half;
        if (lessThan(container.at(middle), value))
        {
            begin = middle + 1;
            n -= half + 1;
        }
        else
        {
            n = half;
        }
    }
    return begin;
}

template <typename Container, typename Type>
int ContainerHelper::lowerBound (const Container& container, const Type &value)
{
    return lowerBound(container, value, qLess<Type>());
}

// Performs a binary search on the container and returns the position of the one-past-the-last occurrence
// of value. If no such item is found, returns the position where the item should be inserted.
// The items in the container must be sorted in ascending order.
// Similar to qUpperBound, but returns integer instead of iterator.
template <typename Container, typename Type>
int ContainerHelper::upperBound (const Container& container, const Type &value)
{
    int begin = 0;
    int n = container.size();
    while (n > 0)
    {
        int half = n >> 1;
        int middle = begin + half;
        if (value < container.at(middle))
        {
            n = half;
        }
        else
        {
            begin = middle + 1;
            n -= half + 1;
        }
    }
    return begin;
}

template <typename Container>
QVariantList ContainerHelper::toVariantList (const Container& container)
{
    QVariantList variantList;
    for (int i = 0; i < container.size(); i++)
        variantList.append(QVariant(container.at(i)));
    return variantList;
}

#ifndef QT_NO_DEBUG
template <typename Container>
bool ContainerHelper::isSorted (const Container& container)
{
    Container containerHelper(container);
    qSort(containerHelper);
    return container == containerHelper;
}


template <typename Container, typename LessThan>
bool ContainerHelper::isSorted (const Container& container, LessThan lessThan)
{
    Container containerHelper(container);
    qSort(containerHelper.begin(), containerHelper.end(), lessThan);
    return container == containerHelper;
}
#endif

template <typename Container, typename LessThan>
void qSort (Container& container, LessThan lessThan)
{
    qSort(container.begin(), container.end(), lessThan);
}

class StringNumericalLess
{
public:
    StringNumericalLess (Qt::CaseSensitivity caseSensitivity = Qt::CaseInsensitive, bool localeAware = true);
    bool operator() (QString left, QString right) const;

private:
    static QPair<int,int> numberFrom (const QString& text, int position);
    Qt::CaseSensitivity m_caseSensitivity;
    bool m_localeAware;
};

#endif // CONTAINERHELPER_H
